package com.zk.algorithm.array;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.BianChengZhiMei;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.Medium;

/**
 * 某个数字出现次数超过一半
 */
@Medium
@LeetCodeExplore
@BianChengZhiMei
public class MajorityElement {

    public static void main(String...args) {
        Utils.println(new MajorityElement().majorityElement2(new int[]{1,2,1,3,1}));
    }

    // ===============================
    // 解法一
    // 数组排序后，中间数字就是最终答案，即第 n/2 大的数字
    // 快速排序 Partition 算法 O(n) 算法得到数组中任意第 k 大的数字
    // ===============================

    public int majorityElement2(int[] nums) {
        KthLargestElementInAnArray kthLargestElementInAnArray = new KthLargestElementInAnArray();
        // 1 1 1 2 3
        //       ↑
        //   第 2 大值
        //     ↑
        return kthLargestElementInAnArray.findKthLargest3(nums, nums.length / 2 + 1);
    }

    // ===============================
    // 次数为 0 的时候，nums[i] 当做候选值，相同 count++，不相同 count--
    // O(n)
    // ===============================

    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;

        for (int i = 1; i < nums.length; i++) {
            // ================
            // no candidate
            // ================
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }

}
